package main.Trie;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

/**
 * <p>A structure which represents a single node within a AbstractTrie. It is typically
 * used by the AbstractTrie and should not need to be manipulated by outside code, except that
 * which extends AbstractTrie. Generally a derivative of AbstractTrie is associated with exactly
 * one subclass of AbstractTrieNode. </p>
 * 
 * @author Brett McLean
 * @author Jared Hance
 * @param <E> the type of value to be stored in this node.
 * @see com.brettbits.structures.trie.Trie
 */
public abstract class AbstractTrieNode<N extends AbstractTrieNode<N, E>, E> implements Comparable<N>, Serializable {

	protected ArrayList<N> childNodes;
    protected char key;
    protected E value;
    protected static final char NULL_KEY = '\u0000';

    /**
     * Create a node with no key and no value
     */
    public AbstractTrieNode() {
        this(NULL_KEY, null);
    }

    /**
     * Create a node with no value and the parameterized key
     * @param key the single character key associated with this node
     */
    public AbstractTrieNode(char key) {
        this(key, null);
    }

    /**
     * Create a node with no key and the parameterized value
     * @param value the value to associate with this node
     */
    public AbstractTrieNode(E value) {
        this(NULL_KEY, value);
    }

    /**
     * Create a Trie node and assign it a key and value
     * @param key the single character key associated with this node
     * @param value the value given to this node
     */
    public AbstractTrieNode(char key, E value) {
        childNodes = new ArrayList<N>();
        this.key = key;
        this.value = value;
    }
    
    /**
     * Create a new empty node.
     * @return
     */
    public abstract N createNode();
    
    /**
     * Create a new node with the given key and value.
     * @param key
     * @param value
     * @return
     */
    public abstract N createNode(char key, E value);

    /**
     * Create and add a child node to the current node, and assign the given key
     * to that new child. This method does not assign a value to the new child
     * node.
     * @param key the single character key to be assigned to the newly
     * created child node.
     * @return the TrieNode structure which represents the newly created
     * child node.
     */
    public N addChild(char key) {
        return addChild(key, null);
    }

    /**
     * Create and add a child node to the current node, assigning both a key
     * and value to that new child.
     * @param key the single character key to be assigned to the newly created
     * child node.
     * @param value the value to be associated with the newly created child node.
     * @return the TrieNode structure which represents the newly created
     * child node.
     */
    public N addChild(char key, E value) {
        N newNode = createNode(key, value);
        addChild(newNode);
        return newNode;
    }

    /**
     * Add the parameterized TrieNode as a child of this node.
     * @param newChild the new TrieNode to add as a child of this node.
     * @return the TrieNode which was just added as a child of this node.
     * This is necessarily always equal to the newChild parameter. i.e.
     * parentNode.addChild(newChild).equals(newChild) is always true.
     */
    private N addChild(N newChild) {
        /* stores the existing child node, if it is found */
        N existingNode = findChild(newChild.getKey());

        if (existingNode == null) { //if this key does not already exist
            childNodes.add(newChild);
        } else { //if this key already existed
            existingNode.setValue(newChild.getValue()); //overwrite the old value
        }
        return newChild;
    }

    /**
     * Removes the child node associated with the given key.
     * @param key the child node associated with this key will be removed.
     * @return the TrieNode object representing the child node which was just
     * removed. Returns null if no child node with the given key existed.
     */
    public N removeChild(char key) {
        N child = findChild(key);
        if(child != null) {
            childNodes.remove(child);
        }
        return child;
    }

    /**
     * Finds and returns a child node with the given key.
     * @param key searches for a child node associated with this single
     * character key.
     * @return the child TrieNode, or null if it is not found.
     */
    public N findChild(char key) {
        N result = null;
        for (N node : childNodes) {
            if (node.getKey() == key) {
                result = node;
                break;
            }
        }
        return result;
    }

    /**
     * Returns whether or not this node has any child nodes.
     * @return whether this node is a leaf (true if it has no child nodes,
     * false otherwise).
     */
    public boolean isLeaf() {
        return childNodes.size() == 0;
    }

    /**
     * Returns whether or not this node has a valid key associated with it.
     * @return true if this node has a valid single character key, otherwise false.
     */
    public boolean hasValidKey() {
        return getKey() != NULL_KEY;
    }


    /**
     * Recursively calculates the number of nodes which are directly or
     * indirectly children of this node, not including this node. A node
     * with no children returns 0 when countDescendants is called. Used to
     * facilitate Trie's getNodeCount method.
     * @return the number of nodes which are directly or
     * indirectly children of this node
     */
    public int countDescendants() {
        int result = 0;
        for (N node : childNodes) {
            result += 1 + node.countDescendants();
        }
        return result;
    }

    /**
     * Recursively generates a string representation of all key/value pairs
     * in the trie rooted at this node, including the key and value of this
     * node. Used to facilitate Trie's toString method.
     * @param key the full key which represents this node.
     * @return a string representation of all key/value pairs in the trie
     * rooted at this node.
     */
    public String toString(String key) {
        Collections.sort(childNodes);
        String result = "";
        if (getValue() != null) {
            result += key + " : " + getValue().toString() + ", ";
        }
        for (N node : childNodes) {
            result += node.toString(key + node.getKey());
        }

        return result;
    }

    /**
     * Recursively searches whether or not a key exists in the trie
     * rooted at this node.
     * @param key the key we are searching for.
     * @return whether or not the key exists in the trie rooted at this node.
     */
    public boolean containsKey(String key) {
        if (key.length() == 0) { //the node was found
            /* The key is said to exist if there is a value at this node. */
            return getValue() != null;
        }

        N childNode = findChild(key.charAt(0));
        if (childNode != null) {
            return childNode.containsKey(key.substring(1));
        }
        return false;
    }

    /**
     * Exhaustively and recursively searches the entire trie rooted at this
     * node for the provided value.
     * @param value the value we are searching for.
     * @return whether or not the value exists in the trie rooted at this node.
     */
    public boolean containsValue(Object value) {
        for (N node : childNodes) {
            if ((node.getValue() != null && node.getValue().equals(value))
                    || node.containsValue(value)) {
                return true;
            }
        }

        return false;
    }

    /**
     * Creates a set of all keys for the sub-Trie rooted at this node.
     * @param keyString the "key so far", as built from parent nodes within the
     * full Trie structure.
     * @return a set containing all String-based keys for the sub-Trie rooted
     * at this node.
     */
    public Set<String> keySet(String keyString) {
        Set<String> result = new LinkedHashSet<String>();
        if(value != null) {
            result.add(keyString);
        }
//        System.out.println("keyString: "+ keyString);
//        System.out.println("childNodes.size: "+ childNodes.size());
        Collections.sort(childNodes);
        for(N child : childNodes) {
            result.addAll(child.keySet(keyString+child.getKey()));
        }
        return result;
    }

    /**
     * Creates a set of all Leaf Nodes keys for the sub-Trie rooted at this node.
     * @param keyString the "key so far", as built from parent nodes within the
     * full Trie structure.
     * @return a set containing all String-based Leaf Node keys for the sub-Trie rooted
     * at this node.
     */
    public Set<String> leafKeySet(String keyString) {
        Set<String> result = new LinkedHashSet<String>();
        if(value != null && this.isLeaf()) {
            result.add(keyString);
        }
        Collections.sort(childNodes);
        for(N child : childNodes) {
            result.addAll(child.leafKeySet(keyString+child.getKey()));
        }
        return result;
    }
    
    /**
     * Creates a equals of all values found in the sub-Trie rooted at
     * this node.
     * @return a collection containing all values for the sub-Trie rooted
     * at this node.
     */
    public Collection<E> values() {
        ArrayList<E> result = new ArrayList<E>();
        if(value != null) {
            result.add(value);
        }
        for(N child : childNodes) {
            result.addAll(child.values());
        }
        return result;
    }

    /**
     * If parameter is a TrieNode, returns whether or not two nodes are equal.
     * Two nodes are said to be equal if they contain the same key and value,
     * regardless of their child or parent nodes.
     * @param obj the node we are comparing against.
     * @return whether or not this node is equal to the parameter node.
     */
    @SuppressWarnings("unchecked")
	@Override
    public boolean equals(Object obj) {
        if(obj instanceof AbstractTrieNode) {
            return equals((N) obj);
        }
        return false;
    }

    /**
     * Returns whether or not two nodes are equal.
     * Two nodes are said to be equal if they contain the same key and value,
     * regardless of their child or parent nodes.
     * @param o the node we are comparing against.
     * @return whether or not this node is equal to the parameter node.
     */
    public boolean equals(N o) {
        return getKey() == o.getKey() && getValue() == o.getValue();
    }

    /**
     * Returns a hash code value for this node.
     * @return a hash code value for this node.
     */
    @Override
    public int hashCode() {
        return getKey() * getValue().hashCode();
    }

    /**
     * Returns a set of all key/value pairs in the trie rooted at this node. The
     * set is guaranteed to be ordered by keys within the trie.
     * @param keyString the full key of this node.
     * @return a set of all key/value pairs in the trie rooted at this node.
     */
    public Set<Map.Entry<String, E>> entrySet(String keyString) {
        Set<Map.Entry<String, E>> result = new LinkedHashSet<Map.Entry<String, E>>();
        if(value != null) {
            AbstractTrie.Entry<String, E> entry = new AbstractTrie.Entry<String, E>(keyString, value);
            result.add(entry);
        }
        Collections.sort(childNodes);
        for(N child : childNodes) {
            result.addAll(child.entrySet(keyString + child.getKey()));
        }
        return result;
    }

    /**
     * Returns a set of all key/value pairs in the trie rooted at this node. The
     * set is guaranteed to be ordered by keys within the trie.
     * @param keyString the full key of this node.
     * @return a set of all key/value pairs in the trie rooted at this node.
     */
    public Set<Map.Entry<String, E>> leafEntrySet(String keyString) {
        Set<Map.Entry<String, E>> result = new LinkedHashSet<Map.Entry<String, E>>();
        if(value != null && this.isLeaf()) {
            AbstractTrie.Entry<String, E> entry = new AbstractTrie.Entry<String, E>(keyString, value);
            result.add(entry);
        }
        Collections.sort(childNodes);
        for(N child : childNodes) {
            result.addAll(child.entrySet(keyString + child.getKey()));
        }
        return result;
    }
    
    /**
     * Returns the single-character key component associated with this node.
     * @return this node's key
     */
    public char getKey() {
        return key;
    }

    /**
     * Returns the value associated with this node.
     * @return this node's value; null if it has no value
     */
    public E getValue() {
        return value;
    }

    /**
     * Sets the key of this node.
     * @param key the key to assign to this node
     */
    public void setKey(char key) {
        this.key = key;
    }

    /**
     * Sets the value associated with this node.
     * @param value the value to assign to this node
     */
    public void setValue(E value) {
        this.value = value;
    }
}
